import java.util.Arrays;

/**
 * 37. 解数独
 * https://leetcode-cn.com/problems/sudoku-solver/
 */
public class Solutions_37 {
    public static void main(String[] args) {
        char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                          {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                          {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                          {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                          {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                          {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                          {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                          {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                          {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        solveSudoku(board);
        System.out.println(Arrays.deepToString(board));
    }

    // rowVisit[0][3] = true，第一行有数字 3 存在
    private static boolean[][] rowVisit = null;
    // colVisit[0][3] = true，第一列有数字 3 存在
    private static boolean[][] colVisit = null;
    // nineGrid[1][2] = true，第二个九宫格中有数字 2 存在
    // i / 3 计算得到是在第 n 行的九宫格上
    // j / 3 计算得到是在第 n 列的九宫格上
    // (i / 3) * 3 + j / 3：得到九宫格所在位置，为 6 时，说明是在第 7 个九宫格上
    private static boolean[][] nineGrid = null;
    public static void solveSudoku(char[][] board) {
        rowVisit = new boolean[9][10];
        colVisit = new boolean[9][10];
        nineGrid = new boolean[9][10];
        // 初始数字，记录到访问数组中
        int c;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    c = board[i][j] - '0';
                    rowVisit[i][c] = true;
                    colVisit[j][c] = true;
                    nineGrid[gridLoc(i, j)][c] = true;
                }
            }
        }
        backtrack(board, 0, 0);
    }

    public static boolean backtrack(char[][] board, int i, int j) {
        // 循环找到需要填空的位置，并进行填空再递归
        while (board[i][j] != '.') {
            if (++j > 8) {
                // 换行
                i ++;
                j = 0;
            }
            // 结束条件：从上往下，从左往右，直到最后一行已经填好
            if (i > 8) {
                return true;
            }
        }
        // 判断 1 ~ 9 数字填在 [i, j] 空格后，是否可以得到正确结果
        for (int k = 1; k <= 9; k++) {
            // 判断 k 是否在所在行，所在列及所在单元格出现过
            boolean rowFlag = rowVisit[i][k];
            boolean colFlag = colVisit[j][k];
            // 计算第 i 行第 j 列所在的九宫格
            int loc = gridLoc(i, j);
            boolean girdFlag = nineGrid[loc][k];
            if (!rowFlag && !colFlag && !girdFlag) {
                // 标记状态
                rowVisit[i][k] = true;
                colVisit[j][k] = true;
                nineGrid[loc][k] = true;
                // 填上数字
                board[i][j] = (char) (k + '0');
                // 递归
                if (backtrack(board, i, j)) {
                    // 逐层返回 true
                    return true;
                }
                // 还原状态
                board[i][j] = '.';
                rowVisit[i][k] = false;
                colVisit[j][k] = false;
                nineGrid[loc][k] = false;
            }
        }
        return false;
    }

    /**
     * 根据 i 行 j 列计算得到所在九宫格的位置
     */
    public static int gridLoc(int i, int j) {
        return (i / 3) * 3 + j / 3;
    }
}
